5897. Sum of squares

For given integers n and m find the sum of squares of all integers, located between n and m inclusively. Print the answer modulo 10⁹ + 9.

Input. Two integers n and m (-10¹⁷ ≤ n, m ≤ 10¹⁷).

Output. Print the sum of squares of all integers between n and m inclusively.

Sample input	Sample output
2 -2	10

SOLUTION

mathematics

Algorithm analysis

Use the formula for the sum of squares:

S(n) = 1² + 2² + … + n² =

Set up the borders of summation so that n ≤ m. If after this m ≤ 0, change the summation interval [n; m] to [-m; -n].

Now we have n ≤ m and m ≥ 0. If n ≥ 0, the desired sum is S(m) – S(n – 1).

If n ≤ 0, the desired sum is S(m) + S(-n).

Algorithm realization

Declare the modulo constant.

#define MOD 1000000009

Function sum computes the sum of squares 1² + 2² + … + n² according to the formula given above. To avoid the overflow in the multiplication, first divide by 6 the numerator, then perform multiplication.

long long sum(long long n)

{

long long a = n % MOD;

long long b = (n + 1) % MOD;

long long c = (2*n + 1) % MOD;

Since n or n + 1 is divisible by 2, then divide by 2 the even multiple.

if (a % 2 == 0) a = a / 2; else b = b / 2;

One of the multiples a = n, b = n + 1 or c = 2n + 1 is necessarily divisible by 3, so divide it by 3.

if (a % 3 == 0) a = a / 3; else

if (b % 3 == 0) b = b / 3; else c = c / 3;

Find the product of factors remaining after the reduction.

return (((a * b) % MOD) * c) % MOD;

}

The main part of the program.

scanf("%lld %lld",&n,&m);

if (n > m) {temp = n; n = m; m = temp;}

if (m < 0) {temp = n; n = -m; m = -temp;}

if (n >= 0)

res = (sum(m) - sum(n-1) + MOD) % MOD;

else

res = (sum(m) + sum(-n)) % MOD;

Print the answer.

printf("%lld\n",res);